<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>两数之和</title>
</head>
<body>
    <script>
        const nums = [2, 7, 11, 15];
        const target = 9;

        // 暴力求解
        function twoSum1 (nums, target) {
            for (let i = 0; i < nums.length; i++) {
                for (let j = i + 1; j < nums.length; j++) {
                    const n1 = nums[i];
                    const n2 = nums[j];
                    // 如果n1,n2之和为目标值 直接返回结果[i, j]
                    if (n1 + n2 === target) {
                        return [i, j];
                    }
                }
            }
            return null;
        }

        // console.log(twoSum1(nums, target)); // [0, 1]

        // 哈希表
        function twoSum2 (nums, target) {
            const mapping = {}; // { 2: 0 }
            for (let i = 0; i < nums.length; i++) {
                // 当前数字
                const num = nums[i]; // 7
                // 要找的数字
                const find = target - num; // 2
                // 如果要找的数字之前被记录过  直接返回结果
                if (mapping[find] !== undefined) {
                    return [ mapping[find], i ];
                }
                // 如果要找的数字之前没有被记录过 记录当前的数字和对应索引
                mapping[num] = i;
            }
        }

        function makeData () {
            return {
                nums: new Array(Math.floor(Math.random() * 100)).map(() => Math.floor(Math.random() * 100)),
                target: Math.floor(Math.random() * 100),
            };
        }

        console.time('暴力求解');
        for (let i = 0; i < 100000; i++) {
            const data = makeData();
            twoSum1(data.nums, data.target);
        }
        console.timeEnd('暴力求解');

        console.time('哈希表');
        for (let i = 0; i < 100000; i++) {
            const data = makeData();
            twoSum2(data.nums, data.target);
        }
        console.timeEnd('哈希表');

    </script>
</body>
</html>